A constraint satisfaction problem (“CSP”) is a mathematical problem that can be solved by satisfying all the constraints of the problem such that the domain of each variable of the problem is narrowed down to a single value without violating any constraint. Each variable has a domain of possible “values,” such as a range of numerical values, an enumerated set of values, a set of items, true/false, etc. Limitations among the variables are expressed as constraints, which act to limit the values that a variable may take.
A constraint solver uses reasoning techniques to find solutions to the CSPs, if any solutions exist. A solution is a state in which the domain of each variable is limited to a single value and no constraint has been violated. A reasoning process includes an “inference” operation, which includes the propagation of the constraints in the attempt to reduce the domain of participating variables, and a “search” operation, which includes making an assignment of a value to each of the variables. By applying reasoning techniques, the constraints are evaluated in order to reduce the domains of the variables. When each domain of the variables is reduced down to a single value without violating any constraints, then a solution to the CSP is found. Thus, a solution to a CSP is a unique assignment of all the variables that satisfies all the constraints of the problem. When a solution is not found, it can be said that the CSP has no solution, or that the CSP is not satisfiable.
“Constraint programming” is a paradigm for solving combinatorial search problems using artificial intelligence, computer science, databases, programming languages, operations research, etc. Currently, constraint programming is applied with success to many different technologies, such as scheduling, planning, vehicle routing, configuration, networks, bioinformatics, etc.
An example of a CSP that normally has a unique solution is Sudoku. In a typical Sudoku puzzle, squares are arranged in a 9×9 grid, where each of the 81 squares represents variables. Each variable is usually defined as an integer having a domain ranging from 1 to 9. The typical Sudoku puzzle includes a first constraint that each row in the grid includes all of the integers 1 through 9 without repeating an integer. A second constraint is that each column in the grid includes all the integers 1 through 9 without repeating an integer. A third constraint is that each of nine 3×3 blocks that are arranged in the grid includes all the integers 1 through 9 without repeating an integer. Given the values for several variables throughout the grid, the remaining variables (squares) can be evaluated using various inference techniques, such as a process of elimination, until a solution to the puzzle can be found. In this example, finding the solution to the Sudoku puzzle includes the filling of the squares with the integers 1 through 9 without violating any of the three constraints.